package 开始的剑指offer8月.面经常用算法题09开始的;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// https://leetcode-cn.com/problems/3sum/
// https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
/*
三数之和
https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
解题方案
思路
标签：数组遍历
首先对数组进行排序，排序后固定一个数 nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L] 和 nums[R]nums[R]，计算三个数的和 sumsum 判断是否满足为 00，满足则添加进结果集
如果 nums[i]nums[i]大于 00，则三数之和必然无法等于 00，结束循环
如果 nums[i]nums[i] == nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sumsum == 00 时，nums[L]nums[L] == nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++L++
当 sumsum == 00 时，nums[R]nums[R] == nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R--R−−
时间复杂度：O(n^2)O(n
2
 )，nn 为数组长度

 */
public class 面经15三数之和0831 {
    // class Solution {
//     public List<List<Integer>> threeSum(int[] nums) {

//             List<List<Integer>> list=new ArrayList<>();
//             if(nums.length==0){
//                 return list;
//             }
//             if(nums.length==1&&nums[0]!=0)
//             return list;
//             int sum=0;
//             for(int i=0;i<nums.length-2;i++){
//                 for(int j=i+1;j<nums.length-1;j++){
//                     for(int k=j+1;k<nums.length;k++){
//                          List<Integer> intlist=new ArrayList<>();
//                             if(sum-nums[i]-nums[j]-nums[k]==0){
//                                // if(nums[i]!=nums[j]&&nums[i]!=nums[k]&&nums[j]!=nums[k]){
//                                 intlist.add(nums[i]);
//                                 intlist.add(nums[j]);
//                                 intlist.add(nums[k]);
//                                 list.add(intlist);
//                                // }

//                             }

//                     }
//                 }
//             }

//             return list;

    //     }
// }
    class Solution {
        public  List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList();
            int len = nums.length;
            if(nums == null || len < 3) return ans;
            Arrays.sort(nums); // 排序
            for (int i = 0; i < len ; i++) {
                if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
                int L = i+1;
                int R = len-1;
                while(L < R){
                    int sum = nums[i] + nums[L] + nums[R];
                    if(sum == 0){
                        ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                        while (L<R && nums[L] == nums[L+1]) L++; // 去重
                        while (L<R && nums[R] == nums[R-1]) R--; // 去重
                        L++;
                        R--;
                    }
                    else if (sum < 0) L++;
                    else if (sum > 0) R--;
                }
            }
            return ans;
        }
    }

}
